package com.darrenchan.leetcode;

/**
 * @Desc
 * @Author chenchi03
 * @CreateTime 2020-01-16 16:10
 */
public class QLint515 {
    public int minCost(int[][] costs) {
        if (costs == null || costs.length == 0) {
            return 0;
        }

        //前i个元素，且最后一个染成j色的最小费用
        //这种写法，牛逼在不用初始化第0元素的值
        int[][] dp = new int[costs.length + 1][3];

        for (int i = 1; i < dp.length; i++) {
            dp[i][0] = Math.min(dp[i - 1][1] + costs[i - 1][0], dp[i - 1][2] + costs[i - 1][0]);
            dp[i][1] = Math.min(dp[i - 1][0] + costs[i - 1][1], dp[i - 1][2] + costs[i - 1][1]);
            dp[i][2] = Math.min(dp[i - 1][0] + costs[i - 1][2], dp[i - 1][1] + costs[i - 1][2]);
        }

        return Math.min(dp[costs.length][0], Math.min(dp[costs.length][1], dp[costs.length][2]));
    }
}
